翻訳と辞書 Words near each other ・ Fixed-odds betting ・ Fixed-pattern noise ・ Fixed-point arithmetic ・ Fixed-point combinator ・ Fixed-point index ・ Fixed-point iteration ・ Fixed-point lemma for normal functions ・ Fixed-point property ・ Fixed-point space ・ Fixed-point subgroup ・ Fixed-point subring ・ Fixed-point theorem ・ Fixed-point theorems in infinite-dimensional spaces ・ Fixed-price contract ・ Fixed-priority pre-emptive scheduling ・ Fixed-radius near neighbors ・ Fixed-rate mortgage ・ Fixed-satellite service ・ Fixed-term contract ・ Fixed-term election ・ Fixed-term Parliaments Act 2011 ・ Fixed-term Work Directive ・ Fixed-wing aircraft ・ Fixedsys ・ Fixedsys Excelsior ・ Fixed–mobile convergence ・ Fixem ・ Fixer ・ Fixer (comics) ・ FiXeR (Download (band) album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fixed-radius near neighbors ： ウィキペディア英語版 Fixed-radius near neighbors In computational geometry, the fixed-radius near neighbor problem is a variant of the nearest neighbor search problem. In the fixed-radius near neighbor problem, one is given as input a set of points in ''d''-dimensional Euclidean space and a fixed distance Δ. One must design a data structure that, given a query point ''q'', efficiently reports the points of the data structure that are within distance Δ of ''q''. The problem has long been studied; cites a 1966 paper by Levinthal that uses this technique as part of a system for visualizing molecular structures, and it has many other applications.〔.〕 One method for solving the problem is to round the points to an integer lattice, scaled so that the distance between grid points is the desired distance Δ. A hash table can be used to find, for each input point, the other inputs that are mapped to nearby grid points, which can then be tested for whether their unrounded positions are actually within distance Δ. The number of pairs of points tested by this procedure, and the time for the procedure, is linear in the combined input and output size when the dimension is a fixed constant. However, the constant of proportionality in the linear time bound grows exponentially as a function of the dimension.〔.〕 Using this method, it is possible to construct indifference graphs and unit disk graphs from geometric data in linear time. The fixed-radius near neighbors problem arises in continuous Lagrangian simulations (such as smoothed particle hydrodynamics), computational geometry, and point cloud problems (surface reconstructions). Modern parallel methods for GPU are able to efficiently compute all pairs fixed-radius NNS. For finite domains, the method of Green shows the problem can be solved by sorting on a uniform grid, finding all neighbors of all particles in O(kn) time, where k is proportional to the average number of neighbors. Hoetzlein improves this further on modern hardware with counting sorting and atomic operations. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fixed-radius near neighbors」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.